A Numerical Algorithm for L2 Semi-Discrete Optimal Transport in 3D
Identifieur interne : 000785 ( Main/Exploration ); précédent : 000784; suivant : 000786A Numerical Algorithm for L2 Semi-Discrete Optimal Transport in 3D
Auteurs : Bruno Lévy [France]Source :
- ESAIM: Mathematical Modelling and Numerical Analysis [ 0764-583X ] ; 2015-11-09.
Abstract
This paper introduces a numerical algorithm to compute the L2 optimal transport map between two measures μ and ν, where μ derives from a density ρ defined as a piecewise linear function (supported by a tetrahedral mesh), and where ν is a sum of Dirac masses. I first give an elementary presentation of some known results on optimal transport and then observe a relation with another problem (optimal sampling). This relation gives simple arguments to study the objective functions that characterize both problems. I then propose a practical algorithm to compute the optimal transport map between a piecewise linear density and a sum of Dirac masses in 3D. In this semi-discrete setting [Aurenhammer et al., Proc. of 8th Symposium on Computational Geometry (1992) 350–357] showed that the optimal transport map is determined by the weights of a power diagram. The optimal weights are computed by minimizing a convex objective function with a quasi-Newton method. To evaluate the value and gradient of this objective function, I propose an efficient and robust algorithm, that computes at each iteration the intersection between a power diagram and the tetrahedral mesh that defines the measure μ. The numerical algorithm is experimented and evaluated on several datasets, with up to hundred thousands tetrahedra and one million Dirac masses.
Url:
DOI: 10.1051/m2an/2015055
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 002208
- to stream Istex, to step Curation: 002178
- to stream Istex, to step Checkpoint: 000019
- to stream Hal, to step Corpus: 000815
- to stream Hal, to step Curation: 000815
- to stream Hal, to step Checkpoint: 000219
- to stream Main, to step Merge: 000774
- to stream Main, to step Curation: 000785
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">A Numerical Algorithm for L2 Semi-Discrete Optimal Transport in 3D</title>
<author><name sortKey="Levy, Bruno" sort="Levy, Bruno" uniqKey="Levy B" first="Bruno" last="Lévy">Bruno Lévy</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:92425551A7A2320FACB59D0CE1A10BDA396405A9</idno>
<date when="2015" year="2015">2015</date>
<idno type="doi">10.1051/m2an/2015055</idno>
<idno type="url">https://api.istex.fr/ark:/67375/80W-XZJ5M18D-K/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">002208</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002208</idno>
<idno type="wicri:Area/Istex/Curation">002178</idno>
<idno type="wicri:Area/Istex/Checkpoint">000019</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000019</idno>
<idno type="wicri:doubleKey">0764-583X:2015:Levy B:a:numerical:algorithm</idno>
<idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-01105021</idno>
<idno type="url">https://hal.inria.fr/hal-01105021</idno>
<idno type="wicri:Area/Hal/Corpus">000815</idno>
<idno type="wicri:Area/Hal/Curation">000815</idno>
<idno type="wicri:Area/Hal/Checkpoint">000219</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000219</idno>
<idno type="wicri:doubleKey">0764-583X:2015:Levy B:a:numerical:algorithm</idno>
<idno type="wicri:Area/Main/Merge">000774</idno>
<idno type="wicri:Area/Main/Curation">000785</idno>
<idno type="wicri:Area/Main/Exploration">000785</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">A Numerical Algorithm for <formula rend="inline"><hi rend="italic">L</hi>
<hi rend="subscript">2</hi>
</formula>
Semi-Discrete
Optimal Transport in 3D</title>
<author><name sortKey="Levy, Bruno" sort="Levy, Bruno" uniqKey="Levy B" first="Bruno" last="Lévy">Bruno Lévy</name>
<affiliation wicri:level="3"><country xml:lang="fr">France</country>
<wicri:regionArea>Inria Nancy Grand-Est and LORIA, rue du Jardin Botanique, 54500 Vandoeuvre</wicri:regionArea>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandoeuvre</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="j" type="main">ESAIM: Mathematical Modelling and Numerical Analysis</title>
<title level="j" type="issue">Optimal Transport</title>
<title level="j" type="abbrev">ESAIM: M2AN</title>
<title level="j" type="publisher-id">m2an</title>
<idno type="ISSN">0764-583X</idno>
<idno type="eISSN">1290-3841</idno>
<imprint><publisher>EDP Sciences</publisher>
<date type="Final-Published" when="2015-11-09">2015-11-09</date>
<date type="Published" when="2015-11">2015-11</date>
<date type="ePublished" when="2015-11-05">2015-11-05</date>
<date type="Published" when="2015-11-05">2015-11-05</date>
<biblScope unit="vol">49</biblScope>
<biblScope unit="issue">6</biblScope>
<biblScope unit="page" from="1693">1693</biblScope>
<biblScope unit="page" to="1715">1715</biblScope>
<biblScope unit="page-count">23</biblScope>
<biblScope unit="ref-count">38</biblScope>
</imprint>
<idno type="ISSN">0764-583X</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0764-583X</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">This paper introduces a numerical algorithm to compute the L2 optimal transport map between two measures μ and ν, where μ derives from a density ρ defined as a piecewise linear function (supported by a tetrahedral mesh), and where ν is a sum of Dirac masses. I first give an elementary presentation of some known results on optimal transport and then observe a relation with another problem (optimal sampling). This relation gives simple arguments to study the objective functions that characterize both problems. I then propose a practical algorithm to compute the optimal transport map between a piecewise linear density and a sum of Dirac masses in 3D. In this semi-discrete setting [Aurenhammer et al., Proc. of 8th Symposium on Computational Geometry (1992) 350–357] showed that the optimal transport map is determined by the weights of a power diagram. The optimal weights are computed by minimizing a convex objective function with a quasi-Newton method. To evaluate the value and gradient of this objective function, I propose an efficient and robust algorithm, that computes at each iteration the intersection between a power diagram and the tetrahedral mesh that defines the measure μ. The numerical algorithm is experimented and evaluated on several datasets, with up to hundred thousands tetrahedra and one million Dirac masses.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
</country>
<region><li>Grand Est</li>
<li>Lorraine (région)</li>
</region>
<settlement><li>Vandoeuvre</li>
</settlement>
</list>
<tree><country name="France"><region name="Grand Est"><name sortKey="Levy, Bruno" sort="Levy, Bruno" uniqKey="Levy B" first="Bruno" last="Lévy">Bruno Lévy</name>
</region>
<name sortKey="Levy, Bruno" sort="Levy, Bruno" uniqKey="Levy B" first="Bruno" last="Lévy">Bruno Lévy</name>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000785 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000785 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Main |étape= Exploration |type= RBID |clé= ISTEX:92425551A7A2320FACB59D0CE1A10BDA396405A9 |texte= A Numerical Algorithm for L2 Semi-Discrete Optimal Transport in 3D }}
This area was generated with Dilib version V0.6.33. |